package BinaryTree;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 苏李涛
 * Date: 2024-07-22
 * Time: 23:01
 */

/**
 *  根据二叉树创建字符串:

 * 给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。
 *
 * 空节点使用一对空括号对 "()" 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：root = [1,2,3,4]
 * 输出："1(2(4))(3)"
 * 解释：初步转化后得到 "1(2(4)())(3()())" ，但省略所有不必要的空括号对后，字符串应该是"1(2(4))(3)" 。
 * 示例 2：
 *
 *
 * 输入：root = [1,2,3,null,4]
 */
public class BinaryTreeExercise1 {

    static class TreeNode {
        public char val;
        public TreeNode left;//储存左孩子的引用
        public TreeNode right;//储存右孩子的引用


        public TreeNode(char val) {
            this.val = val;
        }

    }


    public String tree2str(TreeNode root) {
        if(root == null) {
            return null;
        }

        StringBuilder stringbuilder = new StringBuilder();
        tree2strChild(root, stringbuilder);
        return stringbuilder.toString();

    }

    public void tree2strChild(TreeNode t, StringBuilder stringbuilder) {
        if(t == null) {
            return;
        }
        //先拼接根节点
        stringbuilder.append(t.val);


        if(t.left != null) {
            stringbuilder = stringbuilder.append("(");
            tree2strChild(t.left, stringbuilder);
            //某一边走完，就拼接“）”
            stringbuilder.append(")");
        }else {
            if(t.right == null) {
                return;
            }else {
                //左边为空，右边不为空就拼接 “（）”。
                stringbuilder.append("()");
            }

        }

        if(t.right != null) {
            stringbuilder = stringbuilder.append("(");
            tree2strChild(t.right, stringbuilder);
            //某一边走完，就拼接“）”
            stringbuilder.append(")");
        }else {
            return;
        }
    }
}
